/*
题目链接：https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/
902. 最大为N的数字组合-困难
完成日期：2024/10/5
数位DP
*/
class Solution {
public:
    int a[10];
    long long dp[10];
    int d[10];
    long long dfs(int po,int l,int z){
        if(po==-1)return 1;
        if(!l&&dp[po]!=-1&&!z)return dp[po];
        int up=l?a[po]:9;
        int ans=0;
        for(int i=0;i<=up;++i){
            if(d[i]==0) continue;
            if(i==0&&(!z||(z&&po==0)))continue;
            ans+=dfs(po-1,l&&i==up,z&&i==0);
        }
        return l||z?ans:dp[po]=ans;
    }
    long long solve(int n){
        int pos=0;
        while(n>0){
            a[pos++]=n%10;
            n/=10;
        }
        return dfs(pos-1,1,1);
    }
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        memset(dp,-1,sizeof dp);
        memset(d,0,sizeof d);
        for(auto &v:digits)d[atoi(v.c_str())]=1;
        d[0]=1;
        return solve(n);
    }
};